import java.util.*;

/**
 * @Author 12629
 * @Description：
 */
class Student implements Comparable<Student>{
    public int age;
    public String name;


    //只是比较对象的大小关系 返回值为正数 、 负数 、 0
    @Override
    public int compareTo(Student o) {
        return o.age-this.age;
    }

    //只是比较是否相等  返回值是true 或者 false
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return age == student.age && Objects.equals(name, student.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(age, name);
    }

    @Override
    public String toString() {
        return "Student{" +
                "age=" + age +
                ", name='" + name + '\'' +
                '}';
    }
}

//年龄的比较器
class AgeComparator implements Comparator<Student> {

    @Override
    public int compare(Student o1, Student o2) {
        return o2.age - o1.age;
    }
}

class NameComparator  implements Comparator<Student> {

    @Override
    public int compare(Student o1, Student o2) {
        return o2.name.compareTo(o1.name);
    }
}

class Imp implements Comparator<Integer> {

    @Override
    public int compare(Integer o1, Integer o2) {
        return o2-o1;
    }
}

public class Test {


    /**
     * 时间复杂度：
     *  最坏情况下：O(N^2)  逆序情况下
     *  最好情况下：O(n)   有序的 --》 插入排序 当数据越有序的时候 越快！！
     *  空间复杂度：O(1)
     * 稳定性：
     *    作业！！！！ TODO :
     * @param array
     */
    public static void insertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i-1;
            for (; j >= 0; j--) {
                if(array[j] > tmp) {
                    array[j+1] = array[j];
                }else {
                    //array[j+1] = tmp;
                    break;
                }
            }
            array[j+1] = tmp;
        }

    }

    public static void main(String[] args) {
        int[] array = {1,5,2,9,3,6};
        insertSort(array);
        System.out.println(Arrays.toString(array));
    }


    /**
     * 找到前K个最小的数据！
     *
     * 这个代码 不是真正的 topK的解决方式
     * @param array
     * @param k
     * @return
     */
    //topk问题
    public static int[] smallestK1(int[] array,int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for(int x : array) {
            minHeap.offer(x);
        }
        //小根堆当中 已经把数组所有的元素 存储起来了  k*logn
        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = minHeap.poll();
        }
        return ret;
    }



    //topk建立大根堆,要找小的m个,就先用前m个元素造堆,再一次次判断堆顶
    public static int[] smallestK(int[] array,int k) {

        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k,new Imp());

        for (int i = 0; i < k; i++) {
            maxHeap.offer(array[i]);
        }

        for (int i = k; i < array.length; i++) {
            //1、获取堆顶元素的值
            int top = maxHeap.peek();
            if(top > array[i]) {
                maxHeap.poll();
                maxHeap.offer(array[i]);
            }
        }

        int[] ret = new int[k];

        for (int i = 0; i < k; i++) {
            ret[i] = maxHeap.poll();
        }
        return ret;
    }




    public static void main5(String[] args) {
        Student s1 = new Student();
        s1.age = 10;
        s1.name = "ahagnsan";

        Student s2 = new Student();
        s2.name = "zhagnsan";
        s2.age = 9;

        AgeComparator ageComparator = new AgeComparator();

        NameComparator nameComparator = new NameComparator();
        PriorityQueue<Student> priorityQueue = new PriorityQueue<>(nameComparator);
        priorityQueue.offer(s2);

        priorityQueue.offer(s1);

        Student ret = priorityQueue.poll();
        System.out.println(ret);

    }



    public static void main4(String[] args) {
        PriorityQueue<Integer> priorityQueue1 = new PriorityQueue<>();
        priorityQueue1.offer(11);
        priorityQueue1.offer(2);
        priorityQueue1.offer(3);

        priorityQueue1.poll();



    }
    public static void main3(String[] args) {
        Student s1 = new Student();
        s1.age = 10;
        s1.name = "ahagnsan";
        Student s2 = new Student();
        s2.name = "zhagnsan";
        s2.age = 9;

        AgeComparator ageComparator = new AgeComparator();
        System.out.println(ageComparator.compare(s1, s2));


        NameComparator nameComparator = new NameComparator();
        System.out.println(nameComparator.compare(s1, s2));

    }
    public static void main2(String[] args) {
        Student s1 = new Student();
        s1.age = 10;
        s1.name = "zhagnsan";
        Student s2 = new Student();
        s2.name = "zhagnsan";
        s2.age = 9;

        System.out.println(s1.equals(s2));

        //System.out.println(s1.compareTo(s2));

    }
    public static void main1(String[] args) {
        /*PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();


        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2222);
        //默认分配了一个长度为11的 queue数组
        Queue<Integer> priorityQueue1 = new PriorityQueue<>(list);
        priorityQueue1.offer(11);
        priorityQueue1.offer(2);
        priorityQueue1.offer(3);

        System.out.println(priorityQueue1.poll());
        System.out.println(priorityQueue1.poll());
        System.out.println(priorityQueue1.poll());*/


        Queue<Student> priorityQueue2 = new PriorityQueue<>();
        priorityQueue2.offer(new Student());
        priorityQueue2.offer(new Student());/**/
        //priorityQueue2.offer(null);

    }
}
